package com.ycy;

import java.util.Arrays;

//实现一个上面大 下面小的  优先队列
public class PriorityQueueDemo {

  //定义队列 最大size
  public static final int MAXSIZE = 100;

  //队列中有多少元素
  public int size;

  //从下标1 开始存放元素
  Integer[] value;

  public PriorityQueueDemo(int maxsize) {
    this.value = new Integer[maxsize];
  }

  //新增
  public void add(int value) {
    size++;
    this.value[size] = value;
    //上浮
    upHeap(size);
  }

  public int remove() {
    if (this.size == 0) {
      System.out.println("队列为空");
      return 0;
    }
    int i = this.value[1];

    this.value[1] = this.value[size]; //尾巴放到头部
    this.value[size--] = null;
    downHeap(1);
    return i;
  }

  //下沉
  public void downHeap(int index) {
    int l = index << 1;  //child
    if (l > this.MAXSIZE || l > this.size) { // 超过下标 或者超过元素个数,就可以不下沉了,   ps:心累这个点花了我两个小时 才理解
      return;
    }
    // 1. (l + 1 <= size),这个是必须的 要判断是否能取到右节点
    // 2.左右比较一下去最大的节点
    if ((l + 1 <= size) && less(l, l + 1)) ++l;
    if (less(index, l)) {
      exchange(index, l);
    } else {
      return;
    }
    downHeap(l);
  }

  //上浮
  public void upHeap(int index) {
    int k = index / 2;  //father
    if (k == 0) return;
    if (less(k, index)) {
      exchange(k, index);
    }
    upHeap(k);
  }

  // 2th 比 1th 大 返回true

  public boolean less(int k, int index) {
    return value[k]
            <
            value[index];
  }

  public void exchange(int k, int index) {
    int temp = value[index];
    value[index] = value[k];
    value[k] = temp;
  }


  public static void main(String[] args) {
    PriorityQueueDemo queue = new PriorityQueueDemo(10);
    queue.add(10);
    queue.add(99);
    queue.add(22342343);
    queue.add(100);
    queue.add(55);
    queue.add(55);
    queue.add(1);
    queue.add(100);
    queue.add(2);
    System.out.println(Arrays.toString(queue.value));

    //按排序输出
    while (queue.size != 0) {
      System.out.println(queue.remove());
      System.out.println(Arrays.toString(queue.value));
    }

  }
}
